//拓扑排序中使用的对列和模拟链表的向量
#include <stdio.h>
#include <queue>
#include<vector>
#include<stdlib.h>
using namespace std;
const int maxn=100005;//最多几个点
const int maxm=100005; //最少几条边
vector<int> edge[maxm];//邻接链表
queue<int> Q;//保存入股为0的节点
int an;
int res[maxn];//存下排序后的顺序
int n;//点总数
int inDegree[maxn];//统计每一个节点的入度；

void addedge(int a,int b)
{
    inDegree[b]++;//出现了一条边指向b，所以入度增加1
    edge[a].push_back(b);//
}
void init()
{
    an=0;


    for (int i = 0; i<n; i++)
    {
        inDegree[i] = 0;//刚开始的节点入度均为0
        edge[i].clear();//清除前一组数据的残留
    }

    while (Q.empty()==false)
    {
        Q.pop();//清除之前的数据
    }
}
bool topo()
{
//拓扑排序，判断一个有向图中是否存在环

    for(int i = 0; i<n; i++)
    {
        if (inDegree[i]==0)
        {
            Q.push(i);
        }
    }
    int cnt = 0;
    while (Q.empty()==false)  //当队列中还有入度为0的点
    {
        int newP = Q.front();


        Q.pop();//这里不需要保留拓扑排序的路径，因而不需要保存弹出来的值
        cnt++;
        res[cnt]=newP;
        //printf("%d %d\n",cnt,newP);
        for (int i = 0; i<edge[newP].size(); i++)
        {
            inDegree[edge[newP][i]]--;//去除一条边后，将所指向的后继节点的如度减1
            if (inDegree[edge[newP][i]]==0)
            {
                Q.push(edge[newP][i]);
            }
        }
    }
    if (cnt==n)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

